<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Repeated Solving of an Eplex Problem
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial118.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial115.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial120.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc236">16.4</A>&nbsp;&nbsp;Repeated Solving of an Eplex Problem</H2>
Part of the power of using the eplex library comes from being able to solve
an eplex problem repeatedly after modification.
For example, we can solve the original transportation
problem, add the extra constraint, and resolve the problem.
Remember that as <CODE>eplex_solve/1</CODE> instantiates its argument, we
need to use a new variable for each call:<BR>
<BR>

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
        .... % setup the constraints for the original problem as before
        prob: (A3 + B3 + C3 + D3 =&lt; 40),

        prob: eplex_solver_setup(min(....)), % as before

        prob: eplex_solve(Cost1),     % h. solve original problem
        prob: (A1 $= A2),
        prob: eplex_solve(Cost2),     % i. solve modified problem
        .....
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
Note that posted constraints behave logically: they are added to an eplex
instance when posted, and removed when they are backtracked over.<BR>
<BR>
In the examples so far, the solver has been invoked explicitly.
However, the solver can also behave like a normal constraint, i.e. it is
automatically invoked when certain conditions are met. <BR>
<BR>
As an example, we implement the standard branch-and-bound method of
solving a MIP problem, using the external solver as an LP solver only.
Firstly we outline how this can be
implemented with the facilities we have already encountered. We then show
how this can be improved usin more advanced features of <TT>lib(eplex)</TT>.<BR>
<BR>
With the branch-and-bound approach, a search-tree is formed, and at each node a
`relaxed' version of the MIP problem is solved as an LP problem.
Starting at the root, the problem solved is the original MIP problem, but
without any of the integrality constraints:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- eplex_instance(mip).

main5(Cost, Vars) :-
      % set up variables and constraints, but no integers/1 constraints
      ....
      % assume minimise for simplicity
      mip: eplex_solver_setup(min(Obj)), 
      mip: eplex_solve(RelaxedCost),
      mip: (Cost $&gt;= RelaxedCost),  % RelaxedCost is lower bound 
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
<DIV CLASS="center">
<IMG SRC="tutorial044.gif">
</DIV>
<BR>
<BR>
<DIV CLASS="center">Figure 16.5: Labelling a variable at a MIP tree node</DIV><BR>
<BR>

<A NAME="mipnode"></A>
<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
In general, this initial LP solution contains non-integer assignments
to integer variables. The objective value of this LP is a lower bound on
the actual MIP objective value.
The task of the search is to find integer assignments
for the integer variables that optimises the objective function. 
Each node of the
search-tree solves the problem with extra bound constraints on these
variables. At each node, a particular variable is `labelled' as shown in
Figure&nbsp;<A HREF="#mipnode">16.5</A>. The integer variable in this case has been assigned
the non-integer value of 4.2. In the subsequent nodes of the tree, we
consider two alternate problems, which creates two branches in the search. In one
problem, we impose the bound constraint <I>X</I> &#8804; 4, and in the other, <I>X</I>
&#8805; 5: these are the two nearest integer values to 4.2. In each branch,
the problem is solved
again as an LP problem with its new bound for the variable:<BR>
<BR>

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
branching(IntVars) :-
      ....
      % for each integer variable X which violates the integer constraint
      mip: eplex_var_get(X, solution, XVal),
      ...
      Split is floor(XVal),
      % choice: branch on the two ranges for X
      (mip: (X $=&lt; Split) ; mip: (X $&gt;= Split + 1)),
      mip: eplex_solve(RelaxedCost),
      ...% repeat until there are no integer violations
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
A choice-point for the two alternative branchings is created in the above
code, the problem is solved with one of the branchings (<CODE>X $=&lt; Split</CODE>).
The program then proceeds to further labelling of the variables. The
alternative branch is left to be tried on backtracking.<BR>
<BR>
Eventually, if the problem has a solution, all the integer
variables will be `labelled' with integer values, resulting in a solution to the
MIP problem. However, this will generally not be optimal, and so the program
needs to backtrack into the tree to search for a better solution by trying
the other branches for the variables, using the
existing solution value as a bound.
This `branch-and-bound' search technique is implemented in <TT>lib(branch_and_bound)</TT>.<BR>
<BR>

	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	Remember that ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> provides
libraries that make some programming tasks much easier. There is no
need to write your own code when you can use what is
provided by an ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> library.
	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 16.6: Reminder: use ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> libraries!</DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>

In the code, the external solver is invoked explicitly at every node. This
however may not be necessary as the imposed bound may already be satisfied.
As stated at the start of this section, the invocation of the solver could be done in a
data-driven way, more like a normal constraint.
This is done with <CODE>eplex_solver_setup/4</CODE>:
<CODE>eplex_solver_setup(+Obj,-ObjVal,+Options,+Trigs)</CODE>, a more
powerful version of <CODE>eplex_solver_setup/1</CODE> for setting up a
solver. The <CODE>Trigs</CODE> argument specifies a list of `trigger
modes' for triggering the solver. 
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>&#8857;</B><DD CLASS="dd-description"> <FONT COLOR="#9832CC">See the ECL</FONT><SUP><FONT COLOR="#9832CC"><I>i</I></FONT></SUP><FONT COLOR="#9832CC">PS</FONT><SUP><FONT COLOR="#9832CC"><I>e</I></FONT></SUP><FONT COLOR="#9832CC"> reference manual for a
complete description of the predicate.</FONT>
</DL>


<A NAME="@default420"></A>
For our example, we add a bound constraint at each node to exclude a
fractional solution value for a variable. The criterion we want to use is
to invoke the solver only if this old solution value is excluded by the new
bounds (otherwise the external solver will solve the same problem
redundantly). This is done by
specifying <CODE>deviating_bounds</CODE> in the trigger modes.
The full code that
implements a MIP solution for the
example transportation problem is given below: 

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- lib(eplex).
:- lib(branch_and_bound).

:- eplex_instance(mip).

main6(Cost, Vars) :-
        % b. create the problem variables and set their range
        Vars = [A1,A2,A3,B1,B2,B3,C1,C2,C3,D1,D2,D3], 
        mip: (Vars :: 0.0..1.0Inf),

        % c. post the constraints for the problem to the eplex instance
        mip: (A1 + A2 + A3 $= 21),
        mip: (B1 + B2 + B3 $= 40),
        mip: (C1 + C2 + C3 $= 34),
        mip: (D1 + D2 + D3 $= 10),

        mip: (A1 + B1 + C1 + D1 $=&lt; 50),
        mip: (A2 + B2 + C2 + D2 $=&lt; 30),
        mip: (A3 + B3 + C3 + D3 $=&lt; 40),
        mip: (A1 $= A2),

        % j. post the objective function as a constraint 
        ObjFunc = 10*A1 + 7*A2 + 200*A3 + 
                   8*B1 + 5*B2 + 10*B3 +
                   5*C1 + 5*C2 +  8*C3 + 
                   9*D1 + 3*D2 +  7*D3,
        mip: (ObjFunc  $= Cost),

        % k. this is a more flexible method for setting up a solver.
        %    [deviating_bounds] specifies that the external solver should be
        %    invoked when any solution value is outside the variable bounds 
        mip: eplex_solver_setup(min(ObjFunc), Cost, [], [deviating_bounds]),

        % l. Use the branch_and_bound library to do the branch and bound
        bb_min(( branching(Vars), 
                 mip: eplex_get(cost, Cost)
                 (foreach(V, Vars) do mip: eplex_var_get(V,solution,V))
               ), Cost, _).

branching(IntVars) :-
        % Find a variable X which does not have an integer solution value
        (integer_violation(IntVars, X, XVal) -&gt;
            % m. try the closer integer range first
            Split is round(XVal),
            (Split &gt; XVal -&gt;
                (mip: (X $&gt;= Split) ;  mip: (X $=&lt; Split - 1))
            ;
                (mip: (X $=&lt; Split) ; mip:  (X $&gt;= Split + 1))
            ),
            branching(IntVars)
        ;
            % cannot find any integer violations; found a solution
            true
        ).

% returns Var with solution value Val which violates the integer constraint
integer_violation([X|Xs], Var, Val) :-
        mip: eplex_var_get(X, solution, RelaxedSol),
        % m. we are dealing with floats here, so need some `margin' for a
        %    float value to be considered integer (1e-5 on either side)
        (abs( RelaxedSol - round(RelaxedSol) ) &gt;= 1e-5 -&gt;
            Var = X, Val = RelaxedSol
        ;
            integer_violation(Xs, Var, Val)
        ).

</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
The setup of the solver is done in line <CODE>k</CODE>, with the use of the
<CODE>deviating_bounds</CODE> trigger mode. There are no explicit calls to trigger the
solver &ndash; it is triggered automatically. In addition, the first call to
<CODE>eplex_solve/1</CODE> for an initial solution
is also not required, because when trigger modes are specified, then
by default, <CODE>eplex_solver_setup/4</CODE> will invoke the solver once the
problem is setup. <BR>
<BR>

Besides the <CODE>deviating_bounds</CODE>
trigger condition, the other argument of interest in our use of
<CODE>eplex_solver_setup/4</CODE> is the second argument,
the objective value of the problem (<CODE>Cost</CODE> in the example): 
recall that this was returned previously by <CODE>eplex_solve/1</CODE>.
Unlike in <CODE>eplex_solve/1</CODE>, the variable is <I>not</I>
instantiated when the solver returns. Instead, one of the bounds (lower
bound in the case of minimise) is updated
to the optimal value, reflecting the range the objective value can take,
from suboptimal to the `best' value at optimal. The variable is therefore
made a problem variable by posting of the objective as a constraint in line
<CODE>j</CODE>. This informs the external solver needs to be informed
that the <CODE>Cost</CODE> variable is the objective value.<BR>
<BR>
In line <CODE>m</CODE>, the branch choice is created by the posting of the bound
constraint, which may trigger the external solver. Here, we use a
simple heuristic to decide which of the two branches to try first: the
branch with the integer range closer to the relaxed solution value.
For example, in the situation of Figure&nbsp;<A HREF="#mipnode">16.5</A>, the branch with
<CODE>X $=&lt; 4</CODE> is tried first since the solution value of 4.2 is
closer to 4 than 5.<BR>
<BR>
By using <I>lib(branch_and_bound)</I>'s <CODE>bb_min/3</CODE> predicate in <CODE>m</CODE>, 
there is no need to explicitly write our own branch-and-bound routine. However, 
this predicate requires the cost variable to be instantiated, so we call
<CODE>eplex_get(cost, Cost)</CODE> to instantiate <CODE>Cost</CODE> at the end of
each labelling of the variables. We also get the solution values for the
variables, so that the branch-and-bound routine will remember it.
The final value returned in <CODE>Cost</CODE> (and <TT>Vars</TT> for the solution
values) 
is the optimal value after the branch-and-bound search, i.e. the
optimal value for the MIP problem.<BR>
<BR>

	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	
<UL CLASS="itemize"><LI CLASS="li-itemize">
Use <B>Instance:eplex_solver_setup(+Obj,-ObjVal,+Opts,+Trigs)</B> to
set up an external solver state for instance Instance. Trigs specifies a
list of trigger conditions to automatically trigger the external solver.
<LI CLASS="li-itemize"><B>Instance:eplex_var_get(+Var,+What,-Value)</B> can be used to obtain
information for the variable <B>Var</B> in the eplex instance.
<LI CLASS="li-itemize"><B>Instance:eplex_get(+Item, -Value)</B> can be used to retrieve
information about the eplex instance's solver state.
</UL>

	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 16.7: More advanced modelling in eplex</DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<A NAME="@default421"></A>
Of course, in practice, we do not write our own MIP solver, but 
use the MIP solver provided with the external solvers instead. These
solvers are highly optimised and tightly coupled to their own LP solvers. 
The techniques of solving relaxed subproblems described here are however
very useful for combining the external solver with other solvers in a
hybrid fashion. 
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>&#8857;</B><DD CLASS="dd-description"> <FONT COLOR="#9832CC">See chapter&nbsp;</FONT><A HREF="tutorial121.html#chaphybrid"><FONT COLOR="#9832CC">17</FONT></A><FONT COLOR="#9832CC"> for more details on hybrid techniques.</FONT>
</DL>

<HR>
<A HREF="tutorial118.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial115.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial120.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
